1. Field of the Invention
The present invention relates to computer graphics and, more particularly, to an improved method for rendering three dimensional triangle primitives.
2. Description of Related Art
Computer graphics have many applications. Improvements in computer graphics displays are desirable.
FIG. 1 depicts a conventional computer system 100. The computer system 100 has a processor 102 comprising one or more CPUs, a main memory 104, a disk memory 106, and an input device 108, such as a keyboard and mouse. These devices 102-108 are connected to a bus 120 which transfers data, i.e., instructions and information, between the devices 102-108. A graphics controller 130 is also connected to the bus 120. As shown, the graphics controller 130 includes a drawing processor 132. The drawing processor 132 is also connected to an address generator 134 and a data input of a frame buffer 136 and a Z buffer 138. The address generator 134, in turn, is connected to RAS (row address select) (not shown), CAS (column address select) (not shown), and chip select inputs (not shown) of the frame buffer 136 and Z buffer 138. Illustratively, the frame and Z buffers 136, 138 are implemented with plural VRAMs (video random access memories) or DRAMs (dynamic random access memories). The frame buffer 136 is connected to a display device 140, such as a cathode ray tube (CRT) or liquid crystal display (LCD) monitor.
The drawing processor 132 receives instructions from the processor 102 for drawing objects. For instance, in the case of a computer aided design (CAD) application, the processor 102 may receive user input regarding creating and locating objects in three dimensional (3D) space. The processor 102, in turn, transfers instructions regarding the size, location, texture, translucence, etc. of such objects to the drawing processor 132. In response, the drawing processor 132 creates a picture element (pixel) image representation of a plane of view of such objects in 3D space. The pixels of the image of each plane of view form part of a frame that is stored by the drawing processor 132 in the frame buffer 136. In 3D graphics applications, each pixel has color data (e.g., data for the red, green, and blue values of the pixel), and Z-values, relating to the Z-coordinate, or depth, of a graphical image. The pixel color data is stored in the frame buffer 136. The pixel Z-values are stored in the Z buffer 138. In two dimensional (2-D) applications, the Z-buffer 138 may be used as an additional frame buffer to hold pixel color data. Drawing processors 132 are known, such as is disclosed in U.S. Pat. Nos. 5,046,023 and 5,185,856. The latter reference discloses a drawing processor that is specifically adapted for rendering 3D objects. The contents of these patents are incorporated herein by reference.
One way of drawing 3D representations of polygons is to decompose each polygon into a number of "primitive" shapes, such as lines, polygons, circles, and ellipses. One common primitive is a triangle. Current three 3D computer graphic methods for rendering triangles do not provide high quality images. There are several problems in rendering high quality triangles.
One problem in drawing a triangle is due to the structure of the display device 140 on which graphics are displayed. As seen in FIG. 2, a display device 140 comprises a number of horizontal rows 202 of pixels 204. The display device may be thought of, in effect, as a cartesian coordinate plane wherein the pixels 204 are located at the intersections between lines in the x and y planes (the x and y planes are illustrated with dashed lines).
Excellent quality straight lines may be displayed if the lines are horizontal, vertical, or at a 45.degree. angle with respect to the x-y plane. Difficulties in displaying excellent lines occurs when a line is at an angle other than 45.degree.. (This invention does not involve curved lines or circles, and the difficulties in drawing such lines are not discussed.) As seen in FIG. 3, a line 300 has a slope in which few points fall at intersections (points 302, 304). This means that in many locations along the line, the line does not fall on the screen where there are pixels.
Many methods exist for drawing lines approximating the correct line (these methods are called "edge walking" when drawing a polygon), and are not described in detail. See, for example, Foley, Van Dam, Feiner & Hughes, Computer Graphics Principles and Practice, Chapter 3, Addison-Wesley Publishing Co., 1992. Typically, each time the line increases one unit in either the x or y direction (for example, the y direction), the computer determines the nearest pixel in the perpendicular direction (i.e., the x direction) that is located on that line (i.e., the y plane). For example, when the line 300 crosses line 306 in the y plane, the computer determines that the nearest pixel in the x plane is the pixel 308 directly above. Thus, that pixel is illuminated according to the color, luminescence, etc. of the line being drawn. A second problem with rendering high quality triangles is the drawbacks of existing triangle rendering methods. There are three well known methods for computer graphic rendering of triangles. These methods are (1) span line rendering; (2) triangle drawing; and (3) trapezoid rendering. Span line rendering is performed by drawing a number of lines of varying length. The starting and ending point for each span-line is separately calculated. The edges of each triangle are iterated to produce a set of point-sampled spans. The slopes and starting vertex are used to iterate the pixels forming the span. The large number of calculations results in poor performance (e.g., is slow).
Triangle drawing is performed by sending to the drawing processor the value of each of the three vertices and edge slope. This method is used by many 3D graphics accelerator ASICs currently found in personal computers.
In trapezoid rendering, a polygon is decomposed into a number of trapezoid primitives. Once decomposed, the trapezoids are formed from the two scan lines (a "top" and a "bottom" of the trapezoid) and two line segments (the "sides"). Trapezoids are drawn by stepping down the line segments with two vector generators and filling in all the pixels between them for each scan line.
Each of these methods has drawbacks. Span line rendering has poor performance (e.g., is slow) and without Z error correction, the image quality is poor. If Z error correction is used, the image quality is acceptable, but the performance is further reduced because an error correction value is calculated for each span. The triangle rendering method has a greater performance than the span line method, but has poor image quality because it does not support Z error correction. Trapezoid rendering is difficult because it is difficult to divide a complex polygon into a number of trapezoids. (On the other hand, a complex polygon is easily divided into a number of triangles by simply connecting vertices.) The trapezoid rendering method performs about as well as the triangle drawing method, but has good image quality and performance if used with Z error correction.
Several problems rendering high quality triangles is described with references to one well known method of rendering a 3D triangle are. A triangle typically has one dominant side and two subordinate sides. The dominant side is the side having the greatest range of y values. The triangle 400 shown in FIG. 4A has its dominant side 402 on the left side, and the two subordinate sides 404, 406 to the right. The triangle 450 in FIG. 4B has its dominant side 452 on the right, and the two subordinate sides 454, 456 to the left. Triangles are drawn from the subordinate side to the dominant side. A starting point on the subordinant side and the ending point on the dominant side of each scan line may be calculated.
The vertices on the top and bottom of the dominant side are designated as P1 and P3. The vertex opposite the dominant side is designated P2. Unless P2 is on the same horizontal line (e.g., has the same x value) as either P1 or P3, as seen in FIGS. 4C and 4D, respectively, the triangle is divided into two portions--a top portion and a bottom portion. This is done because the slope of the "line" between P1 and P3 changes at P2 as the y direction increases. It is simpler to edge walk a single slope in the x-y direction. A triangle where P2 has the same y value as P1 or P3 does not have this change in slope problem, and does not need to be divided. To divide a triangle, an imaginary horizontal line is made from P2 to the dominant side. The dashed line 458 in FIG. 4B is such a line.
The "edge walked" polygons form the "outline" of the triangle. The Z values (the apparent "depth" of the triangle) are determined. The triangle is rendered by filling in the scan lines located within the outline according to the proper color and depth. The rendered for 3D shading is a type known as Gourand shading as follows. Each vertex, in addition to having an x, y, and z value, has values for red, green, and blue (R, G, B). The change in RGB values are determined and evenly distributed over the triangle between vertices. A 3D image may also have a translucence (or light transmitting value) (A), and texture values (U,V).
All of the methods discussed have a third drawback, which causes computer generated 3D triangles to appear distorted. This is due in large part to the prior art triangle rendering methods. For example, in prior art methods, every triangle is not drawn in the same direction as every other direction. Rather, the direction the triangle is drawn depends on the shape of the triangle. The method described above, for example, draws triangles from the subordinate side to the dominant side. As seen in FIG. 5, as a result, if a number of triangles are used to form a desired polygon 500 of FIG. 5A, the graphic display 500' of the polygon of FIG. 5B may be drawn having saw-toothed connecting lines 502'.
The reason for this is further explained with reference to FIGS. 5C and 5D. FIG. 5C illustrates a polygon 550. To render a computer graphic representation of this polygon, it may be decomposed into two triangle primitives 552, 554. Because triangles may be drawn from a subordinate side to a dominant side, triangle 552 may be drawn from left to right and triangle 554 may be drawn from right to left. The end point of each scanline may be determined by a horizontal interpolation. Each scanline end point interpolation has a calculation error. Having an error on both sides of the same line (e.g., the common "edge" 556 between the triangles) may result in a saw-toothed edge, as seen in FIG. 5B.
A fourth problem in rendering high quality triangles relates to the apparent depth of the triangle. Prior art methods result in distorted triangles because the display depth value (i.e., the Z value) is not accurate. Thus, when rendering a three dimensional image without back face cuing (removing the polygon "appearing" behind the front polygon before rendering the front polygon), the connecting edges between the front and back faces will show the back face color, which should be hidden behind the front face. If the Z value of the scan line for the back polygon is incorrect, the Z value for the back polygon near the edge is lower (appears to have a depth closer to the screen) than the Z value of the front polygon near the same edge. A desired picture 600 of FIG. 6A has a front face 604 and a back face 604, both triangles having z values connecting at an edge, as seen in the x-z graph of FIG. 6A1. The Z value error results in a graphical representation 650 where the back polygon 652 color at the edge 656 to be shown as if it was located in front of the front polygon 654, as seen in the x-z graph of FIG. 6B1.
Therefore, it is an object of the present invention to provide a method for drawing a 3D computer graphics triangle that eliminates jagged lines at connecting edges.
It is a further object of the present invention to provide a method for drawing a 3D computer graphics triangle wherein connecting edges between front and back faces do not show the back face color.